<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>斐波那契数列</title>
    </head>
    <body>
        <h1>斐波那契数列</h1>
        <script>
            var fib = function (n) {
                if (n < 2) {
                    return n;
                }
                let p = 0,
                    q = 0,
                    r = 1;
                for (let i = 2; i <= n; i++) {
                    p = q;
                    q = r;
                    r = p + q;
                }
                return r;
            };

            function fbnq1(No) {
                let arr = [1, 1];
                if (No <= 2) return 1;
                // 第5个数 算出 下标为4的数 数组长度为5
                while (arr.length < No) {
                    // 获取第几项那就计算最后一项的值 直到数组有几项
                    // 计算倒数第一项和倒数第二项的和 产生新的值
                    arr.push(arr[arr.length - 1] + arr[arr.length - 2]);
                }
                //返回计算好的最后一项
                return arr;
                // return arr[arr.length - 1];
            }

            // 递归 不产生数组
            // 调用次数 计算次数 叠算次数
            function fbnq(No) {
                if (No <= 2) return 1;
                // 第一个数，第二个数 ， 当前是第几个数字
                function fn(last1, last2, curNo) {
                    if (curNo >= No) {
                        return last2;
                    } else {
                        // 原来的第二个数作为第一个数
                        // 加和的最新数作为第二个数
                        // 递归计算下一个数 + 1
                        return fn(last2, last1 + last2, curNo + 1);
                    }
                }
                return fn(1, 1, 2);
            }

            console.log(fbnq(1)); // 1
            console.log(fbnq(2)); // 1
            console.log(fbnq(3)); // 2
            console.log(fbnq(4)); // 3
            console.log(fbnq(5)); // 5
            console.log(fbnq(6)); // 8
            console.log(fbnq(7)); // 13
            console.log(fbnq(8)); // 21
            console.log(fbnq(9)); // 34
            console.log(fbnq(10)); // 55
            console.log(fbnq(11)); // 89
        </script>
    </body>
</html>
